// 要求模数两两互质
// x ≡ a(mod p)
// 令M = p[i] * p[i + 1]...p[n]
// Mi = M / p[i], iMi = inv(Mi)
// Mi * iMi ≡ 1 (mod p[i])
// 每个方程可以看成是ni ≡ a(mod pi)
// 最后不断合并(ni + nj + nk) ≡ a(mod pi)
// 因为nj % pi = 0和 nk% pi = 0，因此不影响原方程
// 答案就是每个方程的ni相加取模M
struct CRT {
  using i64 = long long;
  using i128 = __int128;

  i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (!b) {
      x = 1, y = 0;
      return a;
    }
    i64 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
  }

  i64 work(vector<int> a, vector<int> p) {
    assert(a.size() == p.size());
    i64 M = 1, ret = 0;

    for (int i = 0; i < p.size(); i++) {
      M *= p[i];
    }

    for (int i = 0; i < a.size(); i++) {
      i64 Mi = M / p[i];
      i64 x, y;
      i64 iMi = exgcd(Mi, p[i], x, y);
      x = (x % p[i] + p[i]) % p[i];
      ret += (i128)x * Mi * a[i] % M;
    }
    return ret % M;
  }
};
// crt.work(a, p);